This invention relates to packet communications in a radio-based mesh network, and in particular to techniques for improving throughput of packets via such a network.
In a mesh network, there is an collection of nodes which autonomously connect, send, receive, forward and analyze packetized traffic in the network, which is a shared resource having limitations on traffic capacity. There is a need to optimize performance throughput to the greatest number of users in the network. Heretofore, the nodes have been able to develop performance metrics about themselves and their neighboring nodes which can prove useful in developing throughput improvement schemes. Due to a large installed base of nodes, it is important that new nodes be made backwards compatible with previously installed nodes so that the older nodes are not rendered inoperable.
Mesh packet radio networks are used throughout the world to provide data communication between nodes. These networks are one of several type of data communication network architectures (the other major types being star (e.g., conventional wireline and cellular) and bus (e.g., computer backplane and cable television) and have several advantages over other architectures for providing high capacity data communication over a large area and to a large number of users.
When known radio mesh networks communicate, the radios use a single data rate among all radio that can communicate. There are at least two reasons for using a single data rate:
Hardware simplicity. If the modulation and demodulation hardware operates at but one data rate, it is often much easier and less expensive to implement.
Protocol simplicity. A broadcast on-air protocol supporting only a single data rate is much simpler to design and implement than one intending to coordinate multiple data rates (and, sometimes equivalently, occupied bandwidth) among a plurality of communicating nodes.
Use of a single data rate has permitted implementation of several successful networks, e.g. Metricom""s Ricochet data communication network. These networks occupy a spectra, collect, transport and deliver packets at an acceptable level of performance. This level of performance is in many respects limited by the speed of the constituent links. Extending the performance of these types of networks is the subject of continuing development efforts; this invention teaches the results of one such effort.
Technologies from other environments are known which have been considered as useful in developing solutions to the problems hereinabove described. For example, there are modulation techniques previously considered for PCS radio systems, as in Ue et al., Symbol Rate and Modulation Level Controlled Adaptive Modulation/TDMA/TDD for Personal Communication Systems, IEEE VTE, July 1995, pp. 306-310 (0-7803-3742-X/95). Therein the concern was mainly to combat delay spread, which is the temporal distortion in the time of arrival of a particular bit or symbol of information. The function was to estimate the channel based upon conditions at the transmitter.
Seiichi Sampei, Norihiko Morinaga, and Yukiyoshi Kamio, Adaptive Modulation/TDMA with a BDDFE for 2 Mbp/s Multi-Media Wireless Communication Systems, IEEE VTC""95, July 1995, pg. 311-315. This reference describes a technique whereby a modulation scheme is chosen based upon estimates by or at the transmitter which then xe2x80x9csendsxe2x80x9d the link to a channel preselected to support that modulation scheme.
Patents uncovered during the course of research include the following.
U.S. Pat. No. 5,048,054 to Eyuboglu, et. al. issued Sep. 10, 1991 entitled Line Probing Modem and assigned to Codex Corporation describes an adaptive modem which probes both ends of a link.
U.S. Pat. No. 5,557,644 to Kuwabara issued Sep. 17, 1996 entitled Signal Demodulating and Decoding Apparatus and Signal Demodulating and Decoding Method and assigned to Hitachi, Ltd. describes parallel demodulators.
U.S. Pat. No. 5,490,168 to Phillips, et. al. issued Feb. 6, 1996 entitled Method and System for Automatic Optimization of Data Throughput Using Variable Packet Length and Code parameters and assigned to Motorola, Inc. describes modification of the packet length with changing channel characteristics, with the two xe2x80x9cpredeterminedxe2x80x9d coding rates, using varying packet length, as well as a method for transitioning the receiving and transmitting ends of the link from the xe2x80x9cefficientxe2x80x9d packet to the more xe2x80x9crobustxe2x80x9d (i.e., shorter) packet, and changing between the predetermined coding rates and packet lengths. An alternative includes transitioning from the shorter packets to the longer packets, using counts of the channel errors to change the length of the packets and their related coding rates.
U.S. Pat. No. 5,150,368 to Autruong, et. al. issued Sep. 22, 1992 entitled Minimization of Modem Retransmissions originally assigned to Rolm Systems (now part of Siemens) describes selective retransmission (BEC) with bitwise voting to reach a valid checksum.
U.S. Pat. No. 5,425,051 to Mahany issued Jun. 13, 1995 entitled Radio Frequency Communication Network Having Adaptive Parameters and assigned to Norand Corporation (Cedar Rapids, Iowa) describes an adaptive RF network. U.S. Pat. No. 5,548,821 to Coveley issued Aug. 20, 1996 entitled Adaptive System for Self-Tuning and Selecting a Carrier Frequency in a Radio Frequency Communication System describes an automatic frequency control technique.
Patents uncovered in a survey of keywords include: U.S. Pat. No. 5,432,818 issued Jul. 11, 1995 to Yuang Lou entitled Method and Apparatus of Joint Adaptive Channel Encoding, Adaptive System Filtering, and Maximum Likelihood Sequence Estimation Process by Means of an Unknown Data Training; and U.S. Pat. No. 5,448,593 issued Sep. 5, 1995 to Lawrence Hill, assigned to Cyplex Corporation, entitled Frequency Hopping Time-diversity Communications Systems and Transceivers for Local Area Networks. This patent describes power line carrier communication which uses modulation of frequency pairs selected from sets of pairs. Both ends communicate using the same modulation scheme.
Reference is also made to the prior work of the current inventors, such as Method and System for Routing Packets in a Packet Communication Network Using Locally Constructed Routing Tables, U.S. Pat. No. 5,488,608 issued Jan. 30, 1996; and Method for Routing Packets by Squelched Flooding, U.S. Pat. No. 5,007,052 issued Apr. 9, 1991.
According to the invention, net throughput is optimized on the link between the communicating nodes by dynamically modifying signal characteristics of the signals transmitted between nodes in response to performance metrics which have been determined from analysis at the receivers for the corresponding links. The signal characteristics can be the data rate, modulation type, on-air bandwidth, etc. The performance metrics are calculated based on data-link on-air characteristics of received signals.
In one embodiment, the performance metrics are based upon the historical information about the link that are available at the affected nodes. Each node in the radio network continually collects information regarding measurable on-air characteristics (or specific parameters) while retaining information regarding categories of interference to received packets. The node collects and retains these data both on a per-link and per transmission (specific packets sent and received from a specific node) and a locality-specific basis.
The communication between two nodes has signal characteristics that affect the performance metrics. These signal characteristics include data rate, packet length, modulation type, forward error correction, backwards error correction, bit-wise interleaving, frequency channel selection, power level, block size and/or computational complexity. Probability information can be gathered as a performance metric, such as, a probability of successful transmission between the two nodes, a probability of a bit error in the communication upon receipt at a receiving node, a probability of a packet error in the signal at the receiving node, and a signal strength of the signal at the receiving node. In one embodiment, the data rate of the signal transmitted between the nodes is dependent on a required link signal strength. Some embodiments could communicate between the nodes using spread spectrum transmission.
The optimization is achieved by providing dynamically-varying data rate, modulation techniques, occupied bandwidths, etc., on a per-link basis using intelligent (computer-controlled) radio hardware. The intended receiver dynamically adapts to the signal being received. In one embodiment, the receiver adapts by sensing data rate through a start sequence delivered with each packet where adaptive operation is required.
This start sequence is transmitted with each packet from the transmitting node. The receiving node senses the start sequence of each packet sent to the receiving node. Interpretation of each packet can be adjusted in response to the start sequence in order to adapt to the received signal. For example, the start sequence could indicate a particular modulation technique where the receiving node dynamically adapts to the particular modulation technique indicated by the start sequence.
When a mesh network is created using dynamically varying links according to the invention, the resultant system delivers the highest performance capable of being supported given the topology and propagation extant at the time of the transmission. This variability is designed to be exploited on a per-link basis. This means that a given radio might use a lower data rate for transmitting on a link from, for example, Node A to Link B (Link A= greater than B) while using a higher data rate for transmitting on another link such as from Node A to Node C (Link A= greater than C). Additionally, Node B may (and will often) use a different data rate when communicating back to Node A (Link B= greater than A). Since each radio is capable of several different data rates, each can select the speed that will probabilistically provide the highest net speed.
The foregoing, together with other objects, features and advantages of this invention, will become more apparent when referring to the following specification, claims and the accompanying drawings.